COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	tree.lsp[f81,jmc]	hash trees instead of a-lists
C00006 ENDMK
C⊗;
;;;tree.lsp[f81,jmc]	hash trees instead of a-lists

;;; A hash tree is used to store variables and their values.  It uses
;;; one word less space than an a-list, and look up is logarithmic
;;; in the number of variables if we are not unlucky.
;;; The syntax of a hash tree is
;;; <hash-tree> ::= nil | (<variable>.<value>) | <hash-tree>.<hash-tree>
;;; but this syntax doesn't tell the whole story, because the key
;;; point is that the position in a tree where a <variable>.<value>
;;; pair is stored depends on the hash of the variable.  The hash
;;; range is 0 to 1, and a pair is stored at a point in the tree
;;; determined by how many of its high order bits are needed to
;;; bring about uniqueness.

;;; THE PRESENT VERSION (FOR READING ONLY) DOESN'T ALLOW FOR EQUALITY OF HASHES

;;; The first function looks up the contents of a variable in the tree.
;;; Like  assoc, its value is  NIL  if the variable isn't found and
;;; the pair otherwise.

(defun c (var tree) (c1 (hash var) var tree 0.5 0.25))

(defun c1 (h var tree test delta)
       (if (null tree)
	   nil
	   (atom (car tree))
	   (if (eq var (car tree)) tree nil)
	   (lessp h test)
	   (c1 h var (car tree) (- test delta) (/ delta 2))
	   (c1 h var (cdr tree) (+ test delta) (/ delta 2))))

;;; The second function assigns a value to a variable returning the new tree.
	     
(defun a (var value tree) (a1 (hash var) (cons var value) tree 0.5 0.25))

(defun a1 (h pair tree test delta)
       (if (null tree)
	   pair
	   (atom (car tree))
	   (if (eq (car pair) (car tree))
	       (if (equal (cdr pair) (cdr tree)) tree pair)
	       (a2 h pair (hash (car tree)) tree test delta))
	   (lessp h test)
	   (cons (a1 h pair (car tree) (- test delta) (/ delta 2)) (cdr tree))
	   (cons (car tree) (a1 h pair (cdr tree) (+ test delta) (/ delta 2)))))

(defun a2 (h1 p1 h2 p2 test delta)
       (if (lessp h1 h2)
	   (a3 h1 p1 h2 p2 test delta)
	   (a3 h2 p2 h1 p1 test delta)))

(defun a3 (h1 p1 h2 p2 test delta)
       (lessp h1 test)
       (if (lessp h2 test)
	   (cons (a3 h1 p1 h2 p2 (- test delta) (/ delta 2)) nil)
	   (cons p1 p2))
       (cons nil (a3 h1 p1 h2 p2 (+ test delta) (/ delta 2))))

;;; In the usual applications of hash tables, provision is also made
;;; for deleting an element, but it isn't clear whether the LISP
;;; applications will require this.

;;; Also we may want a RPLAC version of  a.